from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []

        def generate_board(row: List[int]):
            board = []
            for i in range(n):
                board.append('.' * row[i] + 'Q' + '.' * (n-row[i]-1))
            return board

        # return generate_board([1,2,0])
        def backtrack(index, row: List[int]):
            if n == index:
                res.append(generate_board(row))
                return 
            for j in range(n):
                if not col[j] and not dis1[index+j] and not dis2[index-j+n-1]:
                    col[j] = True
                    dis1[index+j] = True
                    dis2[index-j+n-1] = True
                    backtrack(index+1, row+[j])
                    col[j] = False
                    dis1[index+j] = False
                    dis2[index-j+n-1] = False
                    print(col, dis1, dis2)

        col = [False for _ in range(n)]
        dis1 = [False for _ in range(2*n-1)]
        dis2 = [False for _ in range(2*n-1)]
            
        backtrack(0, [])
        return res
print(Solution().solveNQueens(4))